#define _CRT_SECURE_NO_WARNINGS 1

int GetNumberOfK(int* nums, int numsLen, int k) {
    // write code here
    int left = 0;
    int right = numsLen - 1;
    int first = -1;
    int last = -1;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (nums[mid] < k)
        {
            left = mid + 1;
        }
        else {
            if (nums[mid] > k)
            {
                right = mid - 1;
            }
            else {
                --right;
            }
        }
    }
    if (nums[left] == k)
    {
        first = left;
    }
    if (first == -1)
    {
        return 0;
    }
    left = 0;
    right = numsLen - 1;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (nums[mid] < k)
        {
            left = mid + 1;
        }
        else {
            if (nums[mid] > k)
            {
                right = mid - 1;
            }
            else {
                ++left;
            }
        }
    }
    if (nums[left] == k)
    {
        last = right;
    }
    return last - first + 1;
}